package sort_1107;

import java.util.Arrays;

public class Sort {
    public static void quickSort(long[] array) {
        quickSortInternal(array, 0, array.length - 1);  // 左闭右闭区间
    }

    // 左闭右闭：[from, to]
    private static void quickSortInternal(long[] array, int from, int to) {
        // 本次待排序区间的元素个数: to - from + 1
        if (to - from + 1 <= 1) {
            // 待排序区间内的元素个数 <= 1
            // 停止处理这个区间
            return;
        }

        // 选择区间最右边的元素作为 pivot
        // 最右边元素的下标 [to]

        // 进行 partition 的操作
        // 返回值是最终 pivot 的所在下标
        int i = partitionDigHole(array, from, to);

        // 通过 i 这个下标，我们将 [from, to] 这个区间切割成两份
        // 左边的 [from, i - 1] 这里的元素都是 <= pivot
        // 右边的 [i + 1, to]   这里的元素都是 >= pivot
        // 把左右两个小区间按照相同的方式进行处理
        quickSortInternal(array, from, i - 1);
        quickSortInternal(array, i + 1, to);
    }

    /*
    [from, left)  必须保证小于等于基准值
    [left, right) 全部是没有参与过比较的元素
    [right, to]   必须保证大于等于基准值
     */
    private static int partitionHoare(long[] array, int from, int to) {
        long pivot = array[to]; // 选择区间的最右边的元素作为基准值
        int left = from;
        int right = to;

        // 当 [left, right) 区间内还有元素时，循环，得继续
        while (left < right) {  // left < right 只在此处判断了
            // 当选择最右边作为基准值时，优先从左边开始，否则，某些情况下会有元素没有和 pivot 比较过
            while (left < right && array[left] <= pivot) {
                left++;     // left 一直在变，可能破坏 left < right 的约束
            }

            while (left < right && array[right] >= pivot) {
                right--;    // right 一直在变，可能破坏 left < right 的约束
            }

            // array[left] > pivot && array[right] < pivot
            swap(array, left, right);
        }

        /* 真实中的快排不用写这些代码的，只是为了检查正确性约束 */
        assertTrue(left == right, "left 和 right 必须相等");
        assertTrue(left >= from && left <= to, "left 必须在 [from, to] 区间内");

        // 断言 left == right
        // right 的位置就是 pivot 应该所在的下标
        // [right, to] 大于等于基准值
        // 即使交换 [right] 和 [to] 也没有打破 [right, to] 大于等于基准值
        swap(array, right, to);

        // [from, left) 都是小于等于基准值的
        for (int i = from; i < left; i++) {
            assertTrue(array[i] <= pivot, "左边区间的元素必须都是小于等于基准值");
        }
        // [left + 1, to] 都是大于等于基准值的
        for (int i = left + 1; i <= to; i++) {
            assertTrue(array[i] >= pivot, "右边区间的元素都是大于等于基准值");
        }

        return right;   // 最终返回基准值所在的下标
    }

    private static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    private static int partitionDigHole(long[] array, int from, int to) {
        long pivot = array[to];
        int left = from;
        int right = to;

        // 当 [left, right) 区间内还有元素时，循环，得继续
        while (left < right) {
            while (left < right && array[left] <= pivot) {
                left++;
            }

            array[right] = array[left];

            while (left < right && array[right] >= pivot) {
                right--;
            }

            array[left] = array[right];
        }

        /* 真实中的快排不用写这些代码的，只是为了检查正确性约束 */
        assertTrue(left == right, "left 和 right 必须相等");
        assertTrue(left >= from && left <= to, "left 必须在 [from, to] 区间内");
        // [from, left) 都是小于等于基准值的
        for (int i = from; i < left; i++) {
            assertTrue(array[i] <= pivot, "左边区间的元素必须都是小于等于基准值");
        }
        // [left + 1, to] 都是大于等于基准值的
        for (int i = left + 1; i <= to; i++) {
            assertTrue(array[i] >= pivot, "右边区间的元素都是大于等于基准值");
        }

        array[left] = pivot;

        return left;
    }

    private static int partition3(long[] array, int from, int to) {
        /*
        小于基准值的区间范围：       [from, b)
        大于等于基准值的区间范围：[b, d)
        未比较的元素的区间范围：   [d, to)
        基准值                                 [to, to]
         */

        long pivot = array[to];
        // 最开始
        // [from, b) => [from, from)  区间内一个元素都没有
        // [b, d) => [from, from) 区间内一个元素都没有
        // [d, to) => [from, to)  整个区间所有元素都在里面
        int b = from;
        for (int d = from; d < to; d++) {
            if (array[d] < pivot) {
                swap(array, b, d);
                b++;
            }
        }

        swap(array, b, to);

        return b;
    }

    public static void 进阶版Partition(long[] array, int from, int to) {

        long pivot = array[to];
        /*
        [from, b)  小于基准值
        [b, d)     等于基准值
        [d, g]     未比较的元素
        (g, to]    大于基准值
         */

        int b = from;
        int d = from;
        int g = to;

        // [d, g] 这个区间内没有元素时停止； d <= g 说明还有元素
        while (d <= g) {
            if (array[d] == pivot) {
                d++;
            } else if (array[d] < pivot) {
                swap(array, d, b);
                b++;
                d++;
            } else {
                // array[d] > pivot
                swap(array, d, g);
                g--;
            }
        }


    }

    public static void main(String[] args) {
        long[] array = {9, 3, 1, 5, 2, 4, 3, 5, 6, 9, 8, 5, 3, 0, 1, 5};
        进阶版Partition(array, 0, array.length - 1);
    }

    public static void main1(String[] args) {
        long[] array = {9, 5, 1, 7, 3, 8, 2, 0, 6, 4};
        int i = partition3(array, 0, array.length - 1);
    }

//    public static void main(String[] args) {
//        long[] array = { 9, 4, 1, 7, 8, 0, 2, 3, 5, 6 };
//        quickSort(array);
//        System.out.println(Arrays.toString(array));
//    }

    private static void assertTrue(boolean condition, String message) {
        if (!condition) {
            throw new RuntimeException(message);
        }
    }
}
